/**
 * Created with IntelliJ IDEA.
 * Description:最小覆盖子串
 * User: bjc
 * Date: 2025-11-13
 * Time: 13:59
 */
public class Test08_minWindow {
    public String minWindow(String s, String t) {
        if(s.length() < t.length()) return ""; //子串长度比主串大，直接返回
        int[] hash_s = new int[128]; //统计窗口中字符的频次
        int[] hash_t = new int[128];
        int kinds = 0; //记录字符串t中，有多少种字符
        for(int i = 0;i<t.length();i++){ //统计子串中字符出现的次数
            if(hash_t[t.charAt(i)] == 0) kinds++;
            hash_t[t.charAt(i)]++;
        }
        int left = 0,right = 0;
        int count = 0;//记录有效字符的种类
        int ret = Integer.MAX_VALUE;
        int start = 0;
        while (right < s.length()){
            //1.进窗口
            char in = s.charAt(right);
            hash_s[in]++;
            if(hash_s[in] == hash_t[in]) {
                count++;
            }
            //2.判断
            while (count == kinds){
                //3.更新结果
                if(ret > right-left+1){
                    ret = right-left+1;
                    start = left;
                }
                //4.出窗口
                char out = s.charAt(left);
                if(hash_s[out] == hash_t[out]) {
                    count--;
                }
                hash_s[out]--;
                left++;
            }
            right++;
        }
        return ret == Integer.MAX_VALUE ? "" : s.substring(start,start+ret);
    }
}
